<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 工单调度策略（20220413）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>当小区通信设备上报警时&#xff0c;系统会自动生成待处理的工单&#xff0c;华为工单调度系统需要根据不同的策略&#xff0c;调度外线工程师&#xff08;FME&#xff09;上站修复工单对应的问题。</p> 
<p>根据与运营商签订的合同&#xff0c;不同严重程度的工单被处理并修复的时长要求不同&#xff0c;这个要求被修复的时长我们称之为SLA时间。</p> 
<p>假设华为和运营商A签订了运维合同&#xff0c;部署了一套调度系统&#xff0c;只有1个外线工程师&#xff08;FME&#xff09;&#xff0c;每个工单根据问题严重程度会给一个评分&#xff0c;在SLA时间内完成修复的工单&#xff0c;华为获得工单评分对应的积分&#xff0c;超过SLA完成的工单不获得积分&#xff0c;但必须完成该工单。运营商最终会根据积分进行付款。</p> 
<p>请设计一种调度策略&#xff0c;根据现状得到调度结果完成所有工单&#xff0c;让这个外线工程师处理的工单获得的总积分最多。</p> 
<p>假设从某个调度时刻开始&#xff0c;当前工单数量为N&#xff0c;不会产生新的工单&#xff0c;每个工单处理修复耗时为1小时&#xff0c;请设计你的调度策略&#xff0c;完成业务目标。</p> 
<p>不考虑外线工程师在小区之间行驶的耗时。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行为一个整数N&#xff0c;表示工单的数量。</p> 
<p>接下来N行&#xff0c;每行包括两个整数。第一个整数表示工单的SLA时间&#xff08;小时&#xff09;&#xff0c;第二个数表示该工单的积分。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出一个整数表示可以获得的最大积分。</p> 
<p></p> 
<h4 id="%E5%A4%87%E6%B3%A8">备注</h4> 
<ul><li>工单数量N ≤ 10^6</li><li>SLA时间 ≤ 7 * 10^5</li><li>答案的最大积分不会超过2147483647</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<p>假设有7个工单的SLA时间&#xff08;小时&#xff09;和积分如下&#xff1a;</p> 
<table align="center" border="1" cellpadding="1" cellspacing="1" style="width:499px;"><tbody><tr><td style="width:86px;">工单编号</td><td style="width:189px;">SLA</td><td style="width:222px;">积分</td></tr><tr><td style="width:86px;">1</td><td style="width:189px;">1</td><td style="width:222px;">6</td></tr><tr><td style="width:86px;">2</td><td style="width:189px;">1</td><td style="width:222px;">7</td></tr><tr><td style="width:86px;">3</td><td style="width:189px;">3</td><td style="width:222px;">2</td></tr><tr><td style="width:86px;">4</td><td style="width:189px;">3</td><td style="width:222px;">1</td></tr><tr><td style="width:86px;">5</td><td style="width:189px;">2</td><td style="width:222px;">4</td></tr><tr><td style="width:86px;">6</td><td style="width:189px;">2</td><td style="width:222px;">5</td></tr><tr><td style="width:86px;">7</td><td style="width:189px;">6</td><td style="width:222px;">1</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">7<br /> 1 6<br /> 1 7<br /> 3 2<br /> 3 1<br /> 2 4<br /> 2 5<br /> 6 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">15</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">最多可获得15积分&#xff0c;其中一个调度结果完成工单顺序为2&#xff0c;6&#xff0c;3&#xff0c;1&#xff0c;7&#xff0c;5&#xff0c;4&#xff08;可能还有其他顺序&#xff09;</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>用例的含义如下</p> 
<p>从现在开始&#xff1a;</p> 
<ul><li>编号1和2的工单&#xff0c;需要在1小时内完成</li><li>编号5和6的工单&#xff0c;需要在2小时内完成</li><li>编号3和4的工单&#xff0c;需要在3小时内完成</li><li>编号7的工单&#xff0c;需要在6小时内完成</li></ul> 
<p></p> 
<p>如果现在是0点&#xff0c;那么有时间线如下&#xff1a;</p> 
<p><img alt="" height="388" src="https://img-blog.csdnimg.cn/14e5fb91b0e1473b964b51937ecabe76.png" width="441" /></p> 
<p>但是每个工单都需要花费1小时来修复&#xff0c;因此&#xff1a;</p> 
<p></p> 
<ul><li>0~1点之间&#xff0c;工单1和工单2是最优先的&#xff0c;因为超过这个时间&#xff0c;他们即使修复了也没有积分了&#xff0c;但是由于每个工单都需要1小时&#xff0c;因此这个时间段内&#xff0c;只有一个工单可以被修复&#xff0c;另一个工单需要被放弃&#xff0c;此时我们应该选择积分最多的工单2&#xff08;7个积分&#xff09;来优先修复。</li></ul> 
<p>因此这个时间段可以获得7个积分。</p> 
<ul><li>1~2点之间&#xff0c;工单5和工单6是最优先的&#xff0c;但是由于只有1小时&#xff0c;因此只能修复一个工单&#xff0c;优先选择积分高的工单6&#xff08;5个积分&#xff09;来修复。而工单5因为超时所以放弃。</li></ul> 
<p>因此这个时间段可以获得5个积分。</p> 
<ul><li>2~3点之间&#xff0c;工单3和工单4是最优先的&#xff0c;但是由于只有1小时&#xff0c;因此只能修复一个工单&#xff0c;优先选择积分高的工单3&#xff08;2个积分&#xff09;来修复。而工单4因为超时所以放弃。</li></ul> 
<p>因此这个时间段可以获得2个积分。</p> 
<ul><li>3~5点之间&#xff0c;没有紧急工单&#xff0c;这个时间可以处理2个工单&#xff0c;而之前放弃的工单数量有3个&#xff0c;因此我们可以在这段时间内选择处理任意两个放弃掉的工单&#xff0c;但是没有积分拿。</li><li>5~6点之间&#xff0c;有一个紧急工单7&#xff0c;因此我们修复工单7&#xff0c;拿1个积分。</li></ul> 
<p>因此这个时间段可以获得1个积分。</p> 
<ul><li>6~7之间&#xff0c;没有紧急工单&#xff0c;这个时间可以处理1个工单&#xff0c;而之前放弃的工单数量还剩一个&#xff0c;因此我们可以在这段时间选择处理剩下一个被放弃工单&#xff0c;但是没有积分拿。</li></ul> 
<p>最终可以拿到 7 &#43; 5 &#43; 2 &#43; 1 &#61; 15个积分。</p> 
<p></p> 
<p>另外&#xff0c;还有一些其他网友提供的用例如&#xff1a;</p> 
<blockquote> 
 <p>3<br /> 1 1<br /> 2 10<br /> 2 20</p> 
</blockquote> 
<p>当0~1点时&#xff0c;虽然工单1是最紧急的&#xff0c;但是放弃工单1&#xff0c;而是在0~2点执行工单2和3可以获得最大积分30。</p> 
<p>那么上面逻辑该如何实现呢&#xff1f;</p> 
<p></p> 
<p>本题的解题思路可以参照<a href="https://blog.csdn.net/qfc_128220/article/details/128863098?spm&#61;1001.2014.3001.5501" title="LeetCode - 630 课程表Ⅲ_伏城之外的博客-CSDN博客">LeetCode - 630 课程表Ⅲ_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<p>我的解题思路如下&#xff1a;</p> 
<p>首先将所有工单wos按照截止时间升序&#xff0c;即最紧急的排在最前面。</p> 
<p>然后创建一个优先队列pq&#xff08;按照积分升序&#xff0c;即积分少的工单在堆顶&#xff09;&#xff0c;定义一个当前时间curTime &#61; 0&#xff0c;定义一个ans记录拿到的积分&#xff0c;然后遍历升序后的wos的每一个wo并尝试加入pq中&#xff0c;此时会出现两种情况&#xff1a;</p> 
<ul><li>要加入pq的工单wo的截止时间endTime &gt;&#61; curTime &#43; 1&#xff0c;表示当前花一小时修复该工单后&#xff0c;依旧在工单的有效期内&#xff0c;此时我们可以之间将wo加入pq&#xff0c;并且获得该工单的积分 ans &#43;&#61; score&#xff0c;然后curTime&#43;&#43;</li><li>要加入pq的工单wo的截止时间endTime &lt; curTime &#43; 1&#xff0c;表示当前花一个小时修复该工单后&#xff0c;超出了该工单的有效期&#xff0c;此时我们需要比较 优先队列堆顶的工单A的积分&#xff08;优先队列中最小积分&#xff09;和  要加入的B工单的积分&#xff1a;</li></ul> 
<ol><li>如果B &gt; A&#xff0c;则说明当前B工单更具有修复价值&#xff0c;因此我们应该把修复工单A的一小时用来修复B工单&#xff0c;因此优先队列弹出顶部工单A&#xff0c;并加入工单B。此时 ans &#43;&#61; B.score - A.score&#xff0c;而curTime不变&#xff0c;因为只是将原本用于修复A的一小时&#xff0c;换到修复B上。</li><li>如果B &lt;&#61; A&#xff0c;则说明当前B工单不比A更具有修复价值。</li></ol> 
<p></p> 
<p>对于JS而言没有原生的优先队列实现类&#xff0c;基于堆结构实现的优先队列请看&#xff1a;<a href="https://fcqian.blog.csdn.net/article/details/127695013" rel="nofollow" title="LeetCode - 1705 吃苹果的最大数目_伏城之外的博客-CSDN博客">LeetCode - 1705 吃苹果的最大数目_伏城之外的博客-CSDN博客</a></p> 
<p>如果觉得实现过于麻烦&#xff0c;也可以使用有序数组实现优先队列&#xff0c;但是维持优先级的时间复杂度将从O(lgN)升到O(N)</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    n &#61; lines[0] - 0;
  }

  if (n &amp;&amp; lines.length &#61;&#61;&#61; n &#43; 1) {
    const wos &#61; lines.slice(1).map((line) &#61;&gt; line.split(&#34; &#34;).map(Number));
    console.log(getResult(n, wos));
    lines.length &#61; 0;
  }
});

/**
 * &#64;param {*} n 工单数量
 * &#64;param {*} wos 工单的 [SLA, 积分]
 * &#64;returns 可以获得的最大积分
 */
function getResult(n, wos) {
  // 按照SLA截止时间升序
  wos.sort((a, b) &#61;&gt; a[0] - b[0]);

  const pq &#61; new PriorityQueue((a, b) &#61;&gt; a - b);

  let curTime &#61; 0;
  let ans &#61; 0;

  for (let wo of wos) {
    const [endTime, score] &#61; wo;

    if (endTime &gt;&#61; curTime &#43; 1) {
      pq.offer(score);
      ans &#43;&#61; score;
      curTime&#43;&#43;;
    } else {
      if (pq.size() &#61;&#61; 0) {
        continue;
      }

      const min_score &#61; pq.peek();
      if (score &gt; min_score) {
        pq.poll();
        pq.offer(score);
        ans &#43;&#61; score - min_score;
      }
    }
  }

  return ans;
}

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue &#61; [];
    this.cpr &#61; cpr;
  }

  swap(a, b) {
    const tmp &#61; this.queue[a];
    this.queue[a] &#61; this.queue[b];
    this.queue[b] &#61; tmp;
  }

  // 上浮
  swim() {
    let c &#61; this.queue.length - 1;

    while (c &gt;&#61; 1) {
      const f &#61; Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) &lt; 0) {
        this.swap(c, f);
        c &#61; f;
      } else {
        break;
      }
    }
  }

  // 入队
  offer(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f &#61; 0;

    while (true) {
      let c1 &#61; 2 * f &#43; 1;
      let c2 &#61; c1 &#43; 1;

      let c;
      let val1 &#61; this.queue[c1];
      let val2 &#61; this.queue[c2];
      if (val1 &amp;&amp; val2) {
        c &#61; this.cpr(val1, val2) &lt; 0 ? c1 : c2;
      } else if (val1 &amp;&amp; !val2) {
        c &#61; c1;
      } else if (!val1 &amp;&amp; val2) {
        c &#61; c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) &lt; 0) {
        this.swap(c, f);
        f &#61; c;
      } else {
        break;
      }
    }
  }

  // 出队
  poll() {
    this.swap(0, this.queue.length - 1);
    const res &#61; this.queue.pop();
    this.sink();
    return res;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}
</code></pre> 
<p></p> 
<h4 id="Java%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    int[][] wos &#61; new int[n][2];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      wos[i][0] &#61; sc.nextInt();
      wos[i][1] &#61; sc.nextInt();
    }

    System.out.println(getResult(n, wos));
  }

  /**
   * &#64;param n 工单数量
   * &#64;param wos 工单的 [SLA, 积分]
   * &#64;return 可以获得的最大积分
   */
  public static int getResult(int n, int[][] wos) {
    Arrays.sort(wos, (a, b) -&gt; a[0] - b[0]);
    PriorityQueue&lt;Integer&gt; pq &#61; new PriorityQueue&lt;&gt;((a, b) -&gt; a - b);

    int curTime &#61; 0;
    int ans &#61; 0;
    for (int[] wo : wos) {
      int endTime &#61; wo[0];
      int score &#61; wo[1];

      if (endTime &gt;&#61; curTime &#43; 1) {
        pq.offer(score);
        ans &#43;&#61; score;
        curTime&#43;&#43;;
      } else {
        if (pq.size() &#61;&#61; 0) {
          continue;
        }

        int min_score &#61; pq.peek();
        if (score &gt; min_score) {
          pq.poll();
          pq.offer(score);
          ans &#43;&#61; score - min_score;
        }
      }
    }

    return ans;
  }
}</code></pre> 
<p></p> 
<h4 id="Python%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Python算法源码</h4> 
<pre><code class="language-python">import queue

# 输入获取
n &#61; int(input())
wos &#61; [list(map(int, input().split())) for i in range(n)]


# 算法入口
def getResult(wos):
    # 按照SLA截止时间升序
    wos.sort(key&#61;lambda x: x[0])

    pq &#61; queue.PriorityQueue()

    # ans 记录拿到的积分
    ans &#61; 0
    # curTime 记录当前时间
    curTime &#61; 0

    for wo in wos:
        endTime, score &#61; wo

        if endTime &gt;&#61; curTime &#43; 1:
            pq.put(score)
            ans &#43;&#61; score
            curTime &#43;&#61; 1
        else:
            if pq.qsize() &#61;&#61; 0:
                continue

            min_score &#61; pq.queue[0]
            if score &gt; min_score:
                pq.get()
                pq.put(score)
                ans &#43;&#61; score - min_score

    return ans


# 算法调用
print(getResult(wos))</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>